#include "Algorithms.h"
#include <queue>
#include <iostream>

bool operator<(const Edge &a, const Edge &b)
{
	return (a.begin != b.begin ? a.begin < b.begin : a.end < b.end);
}

size_t getGraphAsMatrixByteSize(int vertices)
{
	return sizeof(std::vector<std::vector<bool>>) + sizeof(std::vector<bool>) * vertices + vertices * vertices / 8;
}

size_t getGraphAsListByteSize(int edges, int vertices)
{
	return 2 * sizeof(std::vector<int>) + sizeof(int)* (vertices + edges + 1);
}


std::unique_ptr<IDigraph> makeCompactGraph(const std::vector<Edge> &edges, int vertices_num)
{
	if (getGraphAsMatrixByteSize(vertices_num) > getGraphAsListByteSize(edges.size(), vertices_num))
	{
		std::unique_ptr<IListGraph> list_graph(new IListGraph(edges, vertices_num));
		return std::move(list_graph);
	}
	else
	{
		std::unique_ptr<IMatrixGraph> matrix_graph(new IMatrixGraph(edges, vertices_num));
		return std::move(matrix_graph);
	}
}


void bfs_component(const std::unique_ptr<IDigraph> &graph, int start_vertex, std::unique_ptr<BfsVisitor> &sample_algorithm, std::vector<bool> &is_used)
{
	sample_algorithm->initialize(graph, start_vertex);
	std::queue<int> vertices_order;
	vertices_order.push(start_vertex);
	is_used[start_vertex] = true;
	while (!vertices_order.empty())
	{
		int current_vertex = vertices_order.front();
		sample_algorithm->comeToVertex(current_vertex);
		std::vector<int> adjacent = graph->getIncidenceList(current_vertex);
		for (size_t i = 0; i < adjacent.size(); i++)
		{
			int to = adjacent[i];
			sample_algorithm->processEdge(current_vertex, to);
			if (!is_used[to])
				vertices_order.push(to), is_used[to] = true;;
		}
		vertices_order.pop();
		sample_algorithm->leaveVertex(current_vertex);
	}
	sample_algorithm->finalize();
}

void bfs(const std::unique_ptr<IDigraph> &graph, std::unique_ptr<BfsVisitor> &sample_algorithm)
{
	std::vector<bool> is_used(graph->getNumberOfVertices(), false);
	sample_algorithm->preInit();
	for (int i = 0; i < graph->getNumberOfVertices(); i++)
		if (!is_used[i])
			bfs_component(graph, i, sample_algorithm, is_used);
	for (int i = 0; i < graph->getNumberOfVertices(); i++)
		if (!is_used[i])
			std::cout << "Wrong bfs behaviour (not all vertices were visited)." << std::endl;
}

void dfs_component(const std::unique_ptr<IDigraph> &graph, int start_vertex, std::unique_ptr<DfsVisitor> &sample_algorithm, std::vector<bool> &visited_vertices)
{
	std::vector<int> grey_stack;
	std::vector<std::vector<int>> active_neighbours(graph->getNumberOfVertices());
	sample_algorithm->initialize(graph, start_vertex);
	grey_stack.push_back(start_vertex); visited_vertices[start_vertex] = true;
	active_neighbours[start_vertex] = graph->getIncidenceList(start_vertex);
	while (!grey_stack.empty())
	{
		int from = grey_stack.back();
		sample_algorithm->comeToVertex(from);
		while (!active_neighbours[from].empty())
		{
			int to = active_neighbours[from].back();
			active_neighbours[from].pop_back();
			sample_algorithm->processEdge(from, to);
			if (!visited_vertices[to])
			{
				visited_vertices[to] = true;
				active_neighbours[to] = graph->getIncidenceList(to);
				grey_stack.push_back(to);
				break;
			}
		}
		if (from != grey_stack.back()) continue;
		sample_algorithm->leaveVertex(from);
		grey_stack.pop_back();
	}
	sample_algorithm->finalize();
}

void dfs(const std::unique_ptr<IDigraph> &graph, std::unique_ptr<DfsVisitor> &sample_algorithm)
{
	std::vector<bool> visited_vertices(graph->getNumberOfVertices(), false);
	sample_algorithm->preInit(graph);
	for (int i = 0; i < graph->getNumberOfVertices(); i++)
		if (!visited_vertices[i])
			dfs_component(graph, i, sample_algorithm, visited_vertices);
	for (int i = 0; i < graph->getNumberOfVertices(); i++)
		if (!visited_vertices[i])
			std::cout << "Wrong dfs behaviour (not all vertices were visited)." << std::endl;
}

bool topologicalSort(const std::unique_ptr<IDigraph> &graph, std::vector<int> &order)
{
	std::unique_ptr<DfsVisitor> solution(new DfsTopologicalSort());
	dfs(graph, solution);
	order = dynamic_cast<DfsTopologicalSort*>(solution.get())->getSortedOrder();
	return dynamic_cast<DfsTopologicalSort*>(solution.get())->hasLoop();
}

std::vector<int> solve2SAT(const std::unique_ptr<IDigraph> &graph, int variables)
{
	std::unique_ptr<DfsVisitor> solution(new DfsTarjan);
	std::vector<int> order = dynamic_cast<DfsTarjan*>(solution.get())->getSortedCondesedGraph(graph), position(order.size());
	for (size_t i = 0; i < order.size(); i++)
		position[order[i]] = i;
	std::vector<int> colors = dynamic_cast<DfsTarjan*>(solution.get())->getVerticesColors(graph);
	std::vector<int> result(variables);
	for (int i = 0; i < variables; i++)
	{
		if (colors[i] == colors[variables + i])
		{
			result[0] = -1;
			return result;
		}
		if (position[colors[i]] < position[colors[variables + i]])
			result[i] = 0;
		else
			result[i] = 1;
	}
	return result;
}